package swordoffer.offer03;

public class Solution3_2_1 {
    public static void main(String[] args) {
        int[] nums = new int[1001];
        for (int i = 0;i<nums.length;i++){
            nums[i] = (int)((Math.random()*1000)+1);
        }
        int duplication = getDuplication(nums);
        System.out.println("duplication = " + duplication);
    }
    public static int getDuplication(int[] nums) {
        if (nums == null || nums.length < 0) {
            return -1;
        }
        int start = 1;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = ((end - start) >> 1) + start;
            int count = 0;
            //寻找该区间数字在数组中出现的次数
            for (int num : nums) {
                if (num >= start && num <= mid) {
                    count++;
                }
            }
            //区间只剩一个数字
            if (end == start) {
                //如果该数字出现了两次，就是重复
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            //如果该区间中元素出现的个数，大于区间的最大值，说明该区间存在重复的数字
            if (count > mid - start + 1) {
                //在分割后的左边区间内
                end = mid;
            } else {
                //在分割后的右边区间
                start = mid + 1;
            }
        }
        return -1;
    }
}
